__author__ = 'st316'
'''
Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Corner Cases:
    Did you consider the case where path = "/../"?
    In this case, you should return "/".
    Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
    In this case, you should ignore redundant slashes and return "/home/foo".

# recursion or stack
'''


class Solution:
    # @param path, a string
    # @return a string
    def simplifyPath(self, path):
        if not path:
            return ''
        if path == '/' or path == '/../' or path == '//':
            return '/'
        i = -2
        while path[i] != '/':
            i -= 1
        cur = path[i + 1:-1] if path[-1] == '/' else path[i + 1:]
        if cur == '.' or cur == '/':
            return self.simplifyPath(path[:i + 1])
        elif cur == '..':
            return self.parentDir(self.simplifyPath(path[:i + 1]))
        elif cur == '':  # delete multiple slashes
            return self.simplifyPath(path[:i + 1])
        else:
            pre = self.simplifyPath(path[:i + 1])
            return pre + cur if pre == '/' else pre + '/' + cur

    def parentDir(self, curDir):
        if curDir == '/' or curDir == '/../' or curDir == '//':
            return '/'
        i = -2
        while curDir[i] != '/':
            i -= 1
        cur = curDir[i + 1:-1] if curDir[-1] == '/' else curDir[i + 1:]
        if cur == '..':
            return self.parentDir(curDir[:i + 1])
        else:
            return curDir[:i] if i != -len(curDir) else '/'

    def simplifyPathX(self, path):
        pathes = []
        seg = ''
        for i in xrange(len(path) + 1):
            if i == len(path) or path[i] == '/':
                if seg == "..":
                    if len(pathes) > 0:
                        pathes.pop()
                    else:
                        pass  # return "/"; error, in the test set, this case just ignore
                elif seg == ".":
                    pass  # do nothing
                elif len(seg) > 0:
                    pathes.append(seg)
                seg = ""
            else:
                seg += path[i]
        ret = '/'
        for i in xrange(len(pathes)):
            if i > 0:
                ret += '/'
            ret += pathes[i]
        return ret


if __name__ == '__main__':
    s = Solution()
    print s.simplifyPath('/...')




